This invention relates to the field of computer systems. More particularly, methods are provided for analyzing XACML (eXtensible Access Control Markup Language) policies for the purpose of minimizing, refactoring and/or computing intersections of the policies.
XACML is a standardized access control policy and decision language based on XML (eXtensible Markup Language). It is used to describe access control requirements, shape access control requests, and generate a response to a request based on the requirements.
As indicated by its XML roots, XACML code is hierarchically structured (tree-shaped). Primary components of XACML include PolicySet elements and Policy elements. A PolicySet element is a container for storing Policy elements and/or other PolicySet elements. A Policy element expresses a single access control policy as a set of one or more Rules. Rules contain conditions that are evaluated to either True or False.
When a Subject attempts some Action with regard to a Resource, a Policy Enforcement Point (PEP) (e.g., a filesystem, a web server) forms a request comprising any number of attribute values describing the Subject, the Resource, the Action and the operating Environment. The request is submitted to a Policy Decision Point (PDP), which locates one or more policies that apply to the request and evaluates those policies in light of the attribute values to arrive at a decision to Permit or Deny access.
Because multiple different Policies and/or Rules may apply to a given access request, XACML provides Combining Algorithms that operate to combine decisions or effects of multiple Policies (via a Policy Combining Algorithm) or Rules (via a Rule Combining Algorithm) into a single decision. Thus, application of a Deny-overrides algorithm ensures that if any evaluation (of a Policy or Rule) had the effect of Deny (or, alternatively, if no decision evaluated to Permit), then the final decision is Deny. Similarly, a Permit-overrides algorithm can be used to ensure that the final decision is Permit in the appropriate circumstances.
Another component of XACML is the Target component. A Target is a set of conditions for a Subject, Resource, Action and/or Environment that must be satisfied in order for a particular PolicySet, Policy or Rule to apply to a given access control request. Thus, when a PDP receives a request, it may first identify applicable Targets based on the request's attributes. The associated PolicySet, Policy or Rule for each applicable Target can then be applied.
Rules, Policy elements and PolicySet elements can be very large, complex and difficult to comprehend. The very complexity of an XACML policy may make it difficult to analyze. As the number of rules and policies increases it can become increasingly difficult to manage the access control environment. In general, as individual rules and policies are constructed over time, often to address specific concerns and without much consideration of existing logic, eventually redundant, conflicting and superfluous rules and policies may make it difficult to understand the access control system.
More particularly, it can become very difficult to analyze an XACML policy to determine whether any of the policy's Rules are redundant. That is, is there a pair of Rules in the policy such that for every possible combination of attribute values they will return the same result? It can also be difficult to identify whether any Rules are inconsistent (e.g., one Rule indicates Permit for a given request while the other indicates Deny). Inconsistency is not always an error (a Policy element may specify that one of the Rules has priority over the other), but it may still be helpful to know of conflicting Rules. Other than applying brute force to test every possible combination of attribute values it may not be possible to identify redundant and/or conflicting Rules.
Other information can also be difficult to determine from a Policy, such as which set or sets of attribute values will return a Permit result (for a particular Subject, Resource, Action and/or Environment) and, given a particular set of attribute values, what combination of Subject, Resource, Action and/or Environment might be permitted or denied.
Also, it may be desirable to refactor a policy, that is, rearrange or reorganize individual predicates, conditions, Targets, Rules, Policies and/or PolicySets to create a policy that, while logically equivalent to the original, better satisfies some selected criteria. For example, a policy in which Target elements are configured to address a characteristic of a particular resource may be refactored and populated with Target elements configured to address a characteristic of a subject.
However, no automated mechanism exists to perform such an operation. It may also be desirable to compute the intersection of two policies, that is, determine what set(s) of attribute values will cause both policies to return Permit (or Deny). Other than trying every possible combination of attributes, there is no algorithm for making such a determination.